1. Field of the Invention
The present invention concerns generating and using a color palette, and more particularly, a color palette which can be used for displaying, storing and transmitting color images in a computer or other digital image processing device.
2. Description of the Related Art
To process or display a color image in a computer or other digital image processing device, the color component values for each pixel in the image must be specified. For example, in the RGB (red, green, blue) color space, a color image can be represented by specifying each of the red, green and blue intensity levels for each pixel in the image. In this regard, 8 bits per color have been found to yield visually acceptable results. However, this requires 24 bits per pixel which, given the high resolutions frequently used, can mean that a significant amount of data is required to represent a single color image. Manipulating such a large amount of data requires both a large amount of memory and a large amount of processing time.
Accordingly, conventional techniques have been proposed to use a much smaller set of colors to represent an image. Such a set is conventionally known as a color palette, and often contains 256 different colors. As previously noted, each pixel in a color image is ordinarily represented by 24 bits, which can define 224 or more than 16.7 million different colors. Therefore, by replacing each color in a color image with one of the colors in a 256 color palette, each pixel in a color image can be represented by an 8 bit index into the color palette, rather than 24 bits of color information. Moreover, if the palette colors are selected correctly and a unique palette is used for a particular image, in many cases the image quality is not significantly decreased.
One problem then is how to appropriately select the palette colors. Stated another way, given that 24-bit color image data may have up to 16.7 million colors, the problem is how to select 256 out of those 16.7 million colors that will represent the image well.
Various conventional techniques have been proposed for generating palette colors. However, each has its own problems. For example, some conventional techniques do not in many cases select the palette of colors that would provide good visual results for the subject image. Other conventional techniques ignore small isolated colors, even though such colors may be important to the overall impression of the image. Some other conventional techniques are very computationally intensive, and consequently result in slow processing speeds. With still other techniques, after the palette colors are generated, mapping from the image colors to the palette colors is difficult. That is, after the palette colors have been identified, it is cumbersome to identify for each pixel in the input image which palette color is xe2x80x9cclosestxe2x80x9d to the true image color.
The present invention addresses the foregoing problems by generating a color palette for an image by partitioning the color space into a predetermined number of cells, which is less than the number of colors required in the palette, selecting at least one color from each cell in which an image color exists, and selecting the remaining palette colors based on how the remaining image colors are distributed among the cells.
According to one aspect of the invention, to generate a color palette having m colors (such as 28=256 colors) from a color image described in a color space, pixel image data corresponding to the color image is first obtained. A frequency of occurrence for each color in the pixel image data is then determined. Each color in the pixel image data is assigned to one of a predetermined number (k) of cells into which the color space has been partitioned, where k less than m. For instance, each axis of the color space might be divided into 6 approximately equal-sized intervals, resulting in k=6xc3x976xc3x976=216 rectangular box-shaped cells. The most commonly occurring color is selected in each cell in which a color exists, so as to obtain n palette colors, with nxe2x89xa6k. A vote value is calculated for each unselected color, the vote value being based at least in part on the frequency of occurrence of the color in the pixel image and a weighting factor based on a rank of the color in its corresponding cell, the unselected colors being the colors not selected in the first selecting step. Thereafter, the remaining m-n palette colors are selected as the unselected colors with the highest vote values.
By virtue of the foregoing arrangement, each and every original color in the input color image will have a palette color that is close, regardless of how infrequently an original color occurs. As a result, even colors having a relatively low frequency of occurrence in the image can be closely represented in the palette. Moreover, since each palette color is associated with a cell, a structure is inherently provided for organizing the palette colors, and the input image colors can therefore be readily mapped to corresponding palette colors.
According to a further aspect of the invention, a color palette having m colors (such as 256 colors) is generated from a color image having a number of pixels, each pixel described in a color space. The color of each pixel in the color image is first quantized by zeroing least significant bits of each color component for the pixel. The frequency of occurrence of each quantized color is counted. Each quantized color in the color image is assigned to one of a predetermined number (k) of cells into which the color space has been partitioned, where k less than m. For instance, each axis of the color space might be divided into 6 approximately equal-sized intervals, resulting in k=6xc3x976xc3x976=216 rectangular box-shaped cells. The most commonly occurring quantized color in each cell in which a quantized color exists is selected, based on the count, so as to obtain n palette colors, with nxe2x89xa6k. The unselected colors in each cell are then ranked based on their relative frequencies of occurrence, with higher ranking colors occurring more frequently than lower ranking colors in the same cell, the unselected colors being the quantized colors not selected in the first selecting step. A weighting factor is calculated for each unselected color, the weighting factor being based on the rank of the unselected color, with higher ranking colors receiving a greater weighting factor than lower ranking colors. A vote value is assigned to each unselected color, the vote value being based at least in part on the frequency of occurrence of the quantized color and the assigned weighting factor for the quantized color. Finally, the remaining m-n palette colors are selected as the unselected colors with the highest vote values.
By virtue of the foregoing, the present invention can simultaneously select palette colors so as to produce good visual results for a variety of input images, identify the palette colors quickly, and provide a structure for organizing the palette colors which permits fast mapping of the input image colors.
According to a still further aspect of the invention, input colors in a color image described in a color space are mapped to a reduced palette of m colors derived by partitioning the color space into a predetermined number of cells, there being at least one palette color in each cell that includes an input color. The mapping is performed by determining in which cell each input color lies, and mapping each input color to the closest palette color from among all palette colors in the cell identified for that input color.
By virtue of the foregoing arrangement, the processing time for mapping of colors in an input color image to the selected palette colors can be reduced, since only distances to palette colors in the same cell need to be calculated.
According to more particularized aspects of the invention, the cell in which an input color lies is determined by finding a three-dimensional vector. The vector is determined for each input color by partitioning each color component in the color space into a predetermined number of ranges, and determining into which range each color component of the input color falls.
The foregoing can permit quick identification of the cell in which an color lies, thereby providing even faster mapping of colors in an input color image to the selected palette colors.
This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention can be obtained by reference to the following detailed description of the preferred embodiments thereof in connection with the attached drawings.